package algorithmic_data_structure.动态规划;

/**
 * 给一个数组，求把数组分为最接近的两部分，返回较小部分的和
 * 两部分 元素数量不做要求
 */
public class 平分数组 {
    public static int SplitSumClosed(int[] arr){
        if (arr == null || arr.length < 2) {
            return 0;
        }
        int sum = 0;
        for (int num : arr) {
            sum += num;
        }
//        return processDP(arr, sum / 2);
        return process(arr, 0, sum / 2);
    }
    public static int processDP(int[] arr,int target){
        int[][] dp = new int[arr.length+1][target + 1];
        for (int i = 0; i < target + 1; i++) {
            dp[arr.length][i] = 0; //意思意思
        }
        for (int i = arr.length-1; i >= 0; i--) {
            for (int j = 0; j <= target; j++) {
                dp[i][j] = dp[i+1][j];
                if (j >= arr[i]){
                    dp[i][j] = Math.max(dp[i][j],dp[i+1][j-arr[i]] + arr[i]);
                }
            }
        }
//        PrintUtil.printArray(dp);
        return dp[0][target];
    }
    private static int process(int[] arr, int index, int rest) {
        if (index == arr.length){
//            return rest >= 0 ? 0 : -1;
            return 0;
        }
//        if (rest < 0){
//            return -1;
//        }
        int p1 = process(arr,index+1,rest);
        int p2 = -1;
        //如果是 rest>= arr[index]，后面应该都没机会返回-1了
        if (rest >= arr[index]){
            p2 = process(arr,index+1,rest-arr[index]) + arr[index];
        }
        return Math.max(p1,p2);
    }
}
